/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
/*方法二的人话解释，方法一解释在后边
方法二人话解释：
从方法一我们可以知道，不管n为几，当前n的格雷码中的前一半始终为n - 1的全部，所以这时我们可以忽略n在格雷码中的影响
这时我们将格雷码编号：
[000, 001, 011, 010, 110, 111, 101, 100 ...]
  0,   1,   2,   3 ,   4,   5,  6,   7,  ...
这里的0 ~ 7... 转换为二进制后我们成为二进制码，比如我们要求解5对应的格雷码，这里5对应的二进制码就是0101（5的二进制）
二进制码对应的每一位就是小b，，格雷码每一位是g，这里讲解过程中在前面补0方便理解，这里的\/就是异或的运算
0   0   1   0   1
0   b3  b2  b1  b0
  \/  \/  \/  \/ 
  g3  g2  g1  g0
   0   1   1   1
所以我们由5（0101）推出对应的格雷码为0111
这里解释一下(i >> 1) ^ i，i>>1其实将i每一位向后移动一位，这时和i取异或，相当于和自己的后一位取余
b3 b2  b1  b0  (i)
0  b3  b2  b1  (i >> 1)
g3 g2  g1  g0  (结果) 
方法一的人话解释：

n = 1  [0, 1]
n = 2  [00，01，11，10]
n = 3  [000, 001, 011, 010, 110, 111, 101, 100]
....
一位格雷码只有两个元素，【1， 0】
因为格雷码 n 每增加1，包含的数字会翻倍，这里我们设n位格雷码包含c个数，前一个n为n'，所以c = 2c'
所以这时n中的前c'个数是n'中的所有数字前面补0，相当于全部都是n`中的数字
n = 2  [ 00,  01,  11,  10] 
n = 3  [000, 001, 011, 010] (前四个数)
这时n中的后c'个数是n'中的所有数字前面补1，然后变为逆序
n = 2  [ 00,  01,  11,  10] 
补   1 [100, 101, 111, 110] 
逆  序 [110, 111, 101, 100] （后四个数）
结果拼接
 n = 3  [000, 001, 011, 010, 110, 111, 101, 100]
 */
int* grayCode(int n, int* returnSize){
    int ret_size = 1 << n;
    int *ret = (int *)malloc(ret_size * sizeof(int));
    for (int i = 0; i < ret_size; i++) {
        ret[i] = (i >> 1) ^ i;
    }
    *returnSize = ret_size;
    return ret;
}